#!/usr/bin/env python3
# -*- encoding: utf-8 -*-
"""
@UserFor     :   ***    ***
@File        :   m_1143_最长公共子序列.py    
@Email       :   18574945291@163.com
@Modify Time :   2021-02-15 18:11
@Author      :   code_wizard (wll)

对于子序列问题，第二种动态规划方法是，定义一个 dp 数组，其中 dp[i] 表示到位置 i 为止
的子序列的性质，并不必须以 i 结尾。这样 dp 数组的最后一位结果即为题目所求，不需要再对每
个位置进行统计。
在本题中，我们可以建立一个二维数组 dp，其中 dp[i][j] 表示到第一个字符串位置 i 为止、到
第二个字符串位置 j 为止、最长的公共子序列长度。这样一来我们就可以很方便地分情况讨论这
两个位置对应的字母相同与不同的情况了。
"""

